// 234.回文链表
package LeetcodeHot100;


public class Solution234 {
    public boolean isPalindrome(ListNode head) {
        ListNode index = head;
        int length = 0;
        while (index != null) {
            length++;
            index = index.next;
        }
        length = (length + 1) / 2;
        index = head;
        while (length-- != 0) {
            index = index.next;
        }
        ListNode reverse = reverseList(index);
        for (ListNode node = head; node != null; node = node.next) {
            System.out.println(node.val);
        }
        System.out.println();
        for (ListNode node = reverse; node != null; node = node.next) {
            System.out.println(node.val);
        }

        while (head != null && reverse != null) {
            if (head.val != reverse.val)
                return false;
            head = head.next;
            reverse = reverse.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head) {
        ListNode pre = new ListNode(0);
        while (head != null) {
            ListNode index = head.next;
            head.next = pre.next;
            pre.next = head;
            head = index;
        }
        return pre.next;
    }
}
